This invention relates to a path trace type Viterbi decoder for use in error correction decoding of convolutional codes and to a Viterbi decoding method.
Viterbi decoders for use in maximum likelihood decoding of convolutional codes find applications in transmission systems susceptible to transmission errors such as satellite communications systems and satellite broadcasting because of their high error correction performance. As demodulating circuits evolve in the rate of operation and in the level of integration, low-power, fast Viterbi decoders are in great demand.
FIG. 14 shows an example of a convolutional code encoder having three shift registers 13a-c. This encoder generates from data Y of one bit a convolutional code X1 of one bit and a convolutional code X0 of one bit. The shift register 13a holds data S1 that was inputted earlier than data Y by two data items. The shift register 13b holds data S0 that was inputted earlier than data Y by one data item. The shift register 13c holds data Y that is the currently-inputted data. Code X1 is obtained from data S1 and data Y, which is represented as [1+D.sup.2 ]. Code X0 is found from data S1, data S0, and data Y, which is represented as [1+D+D.sup.2 ]. The number of shift registers contained in an encoder is the encoder constraint length (the number is three in FIG. 14).
The state of the encoder shown in FIG. 14 is determined by two bits, i.e., data S1 held in the shift register 13a and data S0 held in the shift register 13b (the state S1S0). Codes X1 and X0, which are convolutional codes produced in respective states, are univocally defined according to the input data Y. Suppose that FIG. 15(a) shows a situation in which codes X1 and X0 are outputted when data Y is inputted in the state S1S0. In this case, the operation of the encoder of FIG. 14 may be represented by a state transition diagram of FIG. 15(b). For instance, when data 1 is entered in state 01, 10 is produced as a convolutional code and, at the same time, the encoder makes a transition to state 11 by the shift operation of a shift register. The number of encoder states is 2.sup.(K-1) where K is the constraint length of a convolutional code.
The trellis diagram is a diagram in which paths stretching out from respective states are time-arranged in the horizontal direction. FIG. 16 is a trellis diagram that is prepared on the basis of the state transition diagram of FIG. 15(b). With reference to FIG. 16, solid line arrows extending from the individual states 00, 01, 10, and 11 each indicate a path when input data Y is 0 and broken line arrows each indicate a path when input data Y is 1. A point corresponding to a state is called a node.
In Viterbi decoding, a path having a distance nearest to a transmitted code series, known in the art as a most likely path, is found on a trellis diagram such as the one shown in FIG. 16, and decoding processing is carried out by tracing back the most likely path.
For example, with respect to the point a of the trellis diagram of FIG. 16, the encoder is in state 01. This encoder state results from the fact that data 1 is fed in state 00 or the fact that data 1 is fed in state 10. The operation of the encoder at this time is shown in FIG. 17. As can be seen from FIG. 17, input of data 1 in state 00 results in a shift-out of data 0 from the shift register. On the other hand, input of data 1 in state 10 results in a shift-out of data 1 from the shift register. The data shifted out becomes a path select (PS) signal indicative of from which of the states the path arrives. In other words, a PS signal becomes 0 when a path arrives from above (i.e., from state 00) and, on the other hand, it becomes 1 when a path arrives from below (from state 10).
Accordingly, PS signals at nodes through which the most likely path passes become shifted-out signals from the encoder (previously-input signals) and decoding processing is carried out by tracing back the most likely path to find the PS signals at the nodes.
A commonly-used Viterbi decoder is now described below.
A Viterbi decoder was reported in a paper entitled "A 45-Mbit/sec. VLSI Viterbi Decoder for Digital Video Applications," IEEE Natl Telesystems Conf. Vol. 1993, p. 127-130, 93. STANFORD TELECOM. In this Viterbi decoder, a multiported memory is divided into four trace-back memories and the operation of each of the trace-back memories is pipelined with a view to achieving a high-speed and low-power Viterbi decoder.
FIG. 18 illustrates in block form the structure of a conventional Viterbi decoder. 801 is an add-compare-select (ACS) circuit for generating path select (PS) signals from input received codes. 802 is a trace-back memory formed of a multiported memory. 803 is a trace-back circuit. 804 is an address generating circuit. 805 is a timing generating circuit for controlling the operation timing of the entire Viterbi decoder. Trace-back memory 802 is divided into four banks (bank0, bank1, bank 2, bank3). In each bankO-3, the data bit width is 2.sup.(K-1) and the number of words is m, where K is the constraint length of an encoder on the sending side and m is the trace-back length which is used as a trace-back unit in decoding operation.
ACS circuit 801 comprises a branch metric generating means 806 which inputs received codes and generates a plurality of branch metrics, an adder 807, a comparator 808, a selector 809, and a path metric memory 810 for storing a path metric.
With reference to FIG. 19(a), a way of finding a PS signal by ACS circuit 801 is described. FIG. 19(a) is a trellis diagram of an encoder with a constraint length of three, showing only paths indicated by PS signals at respective nodes at respective times. The symbol rate, f, represents the time at which the received code is inputted.
An example case of finding a PS signal at node 2 at time (T0+f), is explained. The path metric of a path which has the possibility of arriving at node 2 at time (T0+f), is first calculated. The path with the possibility of arriving at node 2 at time (T0+f) is a path which passes node 1 or node 3 at time T0. Suppose that the path metric of a path that passes through node 1 at time T0 is PM1 and the path metric of a path that passes through node 3 at time T0 is PM3. The path metrics are stored in path metric storing means 810.
Branch metric generating means 806 generates a plurality of branch metrics for received codes which were entered at time (T0+f). Suppose that the branch metric at the time of branching from node 1 to node 2 is BM12 and the branch metric at the time of branching from node 3 to node 2 is BM32. At this time, the path metric of a path that reaches node 2 by way of node 1 is (PM1+BM12) and the path metric of a path that reaches node 2 by way of node 3 is (PM3+BM32). These add operations are performed in adder 807.
The more likely Path has a lower metric. Two path metrics of two paths are compared in comparator 808. Comparator 808 produces a PS signal corresponding to a path having a smaller path metric. In response to the PS signal received from comparator 808, selector 809 selects a path metric which is then stored in path metric storing means 810.
Since a path, which reaches node 2 by way of node 1, is selected at node 2 in time (T0+f), the PS signal is 0. ACS circuit 801 performs arithmetic operations of PS signals for the respective nodes when the received code is inputted. For this reason, the number of bits of a PS signal produced from ACS circuit 801 is equal to the number of nodes, that is, the number of states of the encoder. In FIG. 19, the number of nodes is 4, for the encoder constraint length is three. Accordingly, the number of PS signal bits becomes four. As shown in FIG. 19(b), the output PS signals from ACS circuit 801 are written into trace-back memory 802 according to the write addresses generated in address generating circuit 804.
Signal decoding by a trace back technique is explained. As described previously, PS signals at nodes through which the most likely path passes become decoded signals, in other words, signal decoding can be carried out by finding a most likely path on a trellis diagram. If a path formed by a solid line of FIG. 19 is a most likely path, then signal decoding can be done by tracing back from node 1 because the most likely path passes node 1 at time (T0+5f).
If the PS signal at node i is PSi, a node number through which the most likely path passes one symbol earlier (j) may be given by: EQU j=PSi.2.sup.(K-2) +[i/2] . . . (Equation 1)
where [x] is the largest integer not exceeding x.
Since the PS signal at node 1 at time (T0+5f) is "0", "0" is produced as a decoded signal. Substituting i=1 and PSi=0 in Equation (1), j=0. This shows that the number of a node through which the most likely path passes at time (T0+4f) is 0. Since the PS signal at node 0 at time (T0+4f) is "1", a "1" is then produced as a decoded signal.
Substituting i=0 and PSi=1 in Equation (1), j=2. This shows that the number of a node through which the most likely path passes at time (T0+3f) is 2. Since the PS signal at node 2 at time (T0+3f) is "1", a "1" is then produced as a decoded signal. Thereafter, the most likely path is traced back in the same way as above and a series of decoded signals becomes {0, 1, 1, 0, 0, 0}. As the decoded signals are obtained in a sequence opposite to that in which the decoded signals were transmitted, the decoded signals are time-relationship reversed to become {0, 0, 0, 1, 1, 0}. By performing a trace-back along the most likely path, signal decoding is carried out.
However, in order to perform a trace-back operation such as the foregoing trace back operation, it is necessary to find a starting node number from which the trace-back operation commences.
FIG. 19(a) shows that all the paths, which arrive at nodes 0 to 3 at time (T0+5f), pass through the same node (i.e., node 0) at time T0. Further, it is obvious that the most likely path before time T0 passes through node 0 at time T0. Generally speaking, the paths, which arrive at their respective nodes, pass through the same node at a past point traced back several times the constraint length K. Accordingly, it is not until time (T0+5f) that the number of a node through which the most likely path passes at time T0 is detected.
Referring now to FIG. 20, the operation of the Viterbi decoder of FIG. 20 is described. FIG. 20(a) shows a most likely path, generated from a receiving code, from time T0 to time T5. FIG. 20(b) shows the operating states of from bank0 to bank3 of trace-back memory 802 from time T0 to time T5.
In State1, m PS signals, generated in ACS circuit 801, are written in each bank of trace-back memory 802. Since bank0 is in State1 in the period from time T0 to time T1, PS signals are written in bank0. Since bank1 is in State1 in the period from time T1 to time T2, PS signals are written in bank1. Likewise, PS signals are written in bank2 in the period from time T2 to time T3 and PS signals are written in bank3 in the period from time T3 to time T4.
To decode a sending signal from the PS signals from time T0 to time T1, it is required to find a node number A through which the most likely path passes at time T1. The node number A can be obtained by tracing back the PS signals from time T1 to time T2 from any node, the reason for which is that all the paths, which pass through their respective nodes at time T2, pass through a specific node through which the most likely path passes at time T1. Such a provisional trace-back is carried out in State2.
Accordingly, the node number A is found when State2 of bank1 ends. When bank1 is in State2, bank2 enters State3 without access.
Finally, in State4, the most likely path is traced back and sending signal decoding is carried out. Bank0 is in State4 in the period from time T3 to time T4. The most likely path is traced back from node A, and the sending signals between time T0 and time T1 are decoded from the result of the trace-back operation. Likewise, bank1 is in State4 in the period from time T4 to time T5, the most likely path is traced back from node B found in State2 of bank2. The sending signals between time T1 and time T2 are decoded from the result of the trace-back operation.
The operating state of each of the banks changes in cycles for decoding operation, in other words the operation of the FIG. 18 Viterbi decoder is pipelined. Trace-back circuit 803 is required to include a time-reversing means because decoding with a trace-back technique is carried out in an opposite order to the sending order.
The received code symbol rate equals the received code decoding rate by such a pipelined trace-back, thereby making it possible to implement fast decoding operations. Additionally, reduction in the consumption of electric power is achieved because trace-back memory 802 can be formed by a conventional RAM.
The prior art Viterbi decoder, however, has the following drawbacks.
In order to provide improved error correction performance in Viterbi decoding, it is necessary to sufficiently increase the trace-back length, m, with respect to the constraint length K. However, greater trace-back length requires greater trace memory storage capacity. In addition, trace-back memory 802 of the FIG. 18 Viterbi decoder requires four banks, which is not preferable in terms of device integration.
Additionally, a multiported memory is employed in the conventional Viterbi decoder, therefore producing the problem that constraints on the speed up of device occur with increasing the size of memory.